#pragma once
#include <iostream>
#include <thread>
#include <mutex>
#include <assert.h>
#include <time.h>
#include <algorithm>
#include<unordered_map>
#include<map>
#include"ObjectPool.h"
using std::cout;
using std::endl;

#ifdef _WIN64
typedef unsigned long long PageId_t;
#elif _WIN32
typedef size_t PageId_t;
// #elif
// Linux
#endif
// threadCache桶的最大个数
static const size_t NFREELIST = 208;
// 桶最大能存内存大小,大于这个数不去threadCache申请内存
static const size_t MAXBITYS = 256 * 1024;
// 页数链表最大为 NPAGES-1
static const size_t NPAGES = 129;
// 一页的大小需要的移位数
static const size_t ShiftPageSize = 13;

inline void *&NextObj(void *obj)
{
    return *(void **)obj;
}
class FreeList
{
public:
    void Push(void *obj)
    {
        assert(obj);

        // 头插
        NextObj(obj) = _freeList;
        _freeList = obj;
        ++_size;
    }
    void PushNumObj(void *start, void *end, size_t num)
    {
        // 头插num数的对象内存
        //  _freeList-> start end node
        NextObj(end) = _freeList;
        _freeList = start;
        
        _size += num;
    }
    void *Pop()
    {
        assert(_freeList);

        void *obj = _freeList;
        _freeList = NextObj(obj);
        --_size;
        return obj;
    }
    void PopNumObj(void *&start, void *&end, size_t num)
    {
        // 头删
        //_freeList-> start end NextObj(end)
        start = _freeList;
        end = start;
        int j = 1;
        for (size_t i = 0; i < num - 1; i++)
        {
            j++;
            end = NextObj(end);
        }
        _freeList = NextObj(end);
        NextObj(end) = nullptr;
        _size -= num;
    }
    bool IsFreeObjToCentral(size_t maxSize)
    {
        return maxSize <= _size;
    }
    bool Empty()
    {
        return _freeList == nullptr;
    }

private:
    void *_freeList = nullptr;
    size_t _size = 0;
};

// 空间映射规则
class SizeClass
{
public:
    // 整体控制在最多10%左右的内碎片浪费
    // [1,128]					8byte对齐	    freelist[0,16)
    // [128+1,1024]				16byte对齐	    freelist[16,72)
    // [1024+1,8*1024]			128byte对齐	    freelist[72,128)
    // [8*1024+1,64*1024]		1024byte对齐     freelist[128,184)
    // [64*1024+1,256*1024]		8*1024byte对齐   freelist[184,208)

    // 映射到哪个桶
    // static size_t _Index(size_t size,size_t alignNum)
    // {
    //     if(size % alignNum == 0)
    //     {
    //         return size/alignNum-1;
    //     }
    //     else{
    //         return size/alignNum;
    //     }
    // }
    
    // 库的实现
    static size_t _Index(size_t bytes, size_t align_shift)
    {
        return ((bytes + (1 << align_shift) - 1) >> align_shift) - 1;
    }
    static size_t Index(size_t size)
    {
        assert(size <= MAXBITYS);
        static size_t group_array[] = {16, 72, 128, 184};
        if (size >= 1 && size <= 128)
        {
            return _Index(size, 3);
        }
        else if (size > 128 && size <= 1024)
        {
            return _Index(size - 128, 4) + group_array[0];
        }
        else if (size > 1024 && size <= 8 * 1024)
        {
            return _Index(size - 1024, 7) + group_array[1];
        }
        else if (size > 8 * 1024 && size <= 64 * 1024)
        {
            return _Index(size - 8 * 1024, 10) + group_array[2];
        }
        else if (size > 64 * 1024 && size <= 256 * 1024)
        {
            return _Index(size - 64 * 1024, 13) + group_array[3];
        }
        else
        {
            assert(false);
        }
    }
    // 对齐数是多少
    // static size_t _RoundUp(size_t size,size_t alignNum)
    // {
    //     size_t alignSize;
    //     if(size % alignNum != 0)
    //     {
    //         alignSize = (size/alignNum+1)*alignNum;
    //     }
    //     else{
    //         alignSize = size;
    //     }
    //     return alignSize;
    // }
    // 库的实现
    static size_t _RoundUp(size_t bytes, size_t alignNum)
    {
        return (bytes + alignNum - 1) & ~(alignNum - 1);
    }
    static size_t RoundUp(size_t size)
    {
        if (size >= 1 && size <= 128)
        {
            return _RoundUp(size, 8);
        }
        else if (size > 128 && size <= 1024)
        {
            return _RoundUp(size, 16);
        }
        else if (size > 1024 && size <= 8 * 1024)
        {
            return _RoundUp(size, 128);
        }
        else if (size > 8 * 1024 && size <= 64 * 1024)
        {
            return _RoundUp(size, 1024);
        }
        else if (size > 64 * 1024 && size <= 256 * 1024)
        {
            return _RoundUp(size, 8 * 1024);
        }
        else
        {
            return _RoundUp(size,1 << ShiftPageSize);
        }
    }
    static size_t HowManyNumObj(size_t size)
    {
        assert(size > 0);
        // 慢启动获取内存数量
        size_t num = MAXBITYS / size;
        if (num > 512)
            num = 512;
        if (num < 2)
            num = 2;

        return num;
    }
    static size_t NumMovePage(size_t size)
    {
        assert(size > 0);
        size_t num = size >> ShiftPageSize;

        if (num < 1)
        {
            num = 1;
        }
        return num;
    }
};

class Span
{
public:
    // 指向申请内存的指针
    void *_freeList = nullptr;
    // span下的分出去的内存个数
    size_t _useCount = 0;

    // 双向循环结构
    Span *_prev = nullptr;
    Span *_next = nullptr;

    // 记录页号和页数
    PageId_t _PageId;
    size_t _n;

    //是否被使用
    bool _isUse = false;

    //span里分割的内存是多大
    size_t _size;
};
// 带头双向循环链表
// 多线程桶锁
class SpanList
{
public:
    SpanList()
    {
        _head->_next = _head;
        _head->_prev = _head;
    }
    Span *Begin()
    {
        return _head->_next;
    }
    Span *End()
    {
        return _head;
    }
    bool IsEmpty()
    {
        return _head == _head->_next;
    }
    void PushFront(Span *span)
    {
        insert(Begin(),span);
        // 头插
        //   head span next
        // Span *next = _head->_next;

        // _head->_next = span;
        // span->_next = next;
        // span->_prev = _head;
        // next->_prev = span;
    }
    Span *PopFront()
    {
        // assert(_head == _head->_next);
		Span* front = _head->_next;
		Erase(front);
		return front;

        // 头删
        //  head node next
        // assert(_head != _head->_next);
        // Span *node = _head->_next;
        // Span *next = node->_next;
        // _head->_next = next;
        // next->_prev = _head;
        // return node;
    }
    void Erase(Span* span)
    {
        assert(span);
        assert(span != _head);

        Span* prev = span->_prev;
        Span* next = span->_next;
        //prev span next
        prev->_next = next;
        next->_prev = prev;
    }
    void insert(Span* node,Span* span)
    {
        assert(node);
		assert(span);
        //prev span node
        Span* prev = node->_prev;
        node->_prev = span;
        span->_next = node;
        span->_prev = prev;
        prev->_next = span;
    }

    inline void Lock()
    {
        _mtx.lock();
    }
    inline void UnLock()
    {
        _mtx.unlock();
    }
    // std::unordered_map<PageId_t,Span*> _spanMap;
private:
    // 用定长内存池解决
    Span *_head = new Span();
    std::mutex _mtx;
};
